package maze;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Way1 {
	
	public static void main(String[] args) {
		Way1 way1 = new Way1();
		final int mazeSize = 10;
		String[][] array = way1.createMaze(mazeSize);//创建原始迷宫
		way1.printMaze(array,mazeSize);//输出原始迷宫图
		way1.bfs(array,mazeSize);//广度优先搜索
		//way1.dfs(array,mazeSize);//深度优先搜索
		way1.printMaze(array,mazeSize);//输出最终迷宫图
	}
	
	/**
	 * 广度优先搜索
	 * @param array 迷宫数组
	 * @param mazeSize 迷宫尺寸
	 */
	public void bfs(String[][] array,int mazeSize) {
		Map<String,String> visitedMap = new HashMap<>();//定义一个集合，存储所有已被访问过的节点
		//java.util.Queue<BfsPoint> queue = new java.util.concurrent.ConcurrentLinkedQueue<>();//一般队列
		//优先队列
		final String endPosition = (mazeSize-1)+","+(mazeSize-1);//终点位置
		PriorityQueue<BfsPoint> queue = new PriorityQueue<>(mazeSize,new Comparator<BfsPoint>() {
			@Override
			public int compare(BfsPoint o1, BfsPoint o2) {
				if(distance(o1.position,endPosition) - distance(o2.position,endPosition) >= 0) {
					return 1;
				}else {
					return -1;
				}
			}
		});
		queue.add(new BfsPoint("0,0",null));//起始位置
		visitedMap.put("0,0","0,0");
		final String[] positions = {"0,-1","0,1","-1,0","1,0"};//左、右、上、下
		int h = 0,v = 0;
		boolean stapFlag = false;
		while((!queue.isEmpty())&&(!stapFlag)) {
			BfsPoint bfsPoint = queue.poll();//出队操作
			String positionSplit[] = bfsPoint.position.split(",");
			int horizontal = Integer.parseInt(positionSplit[0]);
			int vertical = Integer.parseInt(positionSplit[1]);
			//遍历左、右、上、下四个走法
			for(String each:positions) {
				String[] splits = each.split(",");
				h = horizontal + Integer.parseInt(splits[0]);
				v = vertical + Integer.parseInt(splits[1]);
				if(canMove(h,v,mazeSize,array,visitedMap)) {
					if(array[h][v].equals("E")) {
						queue.clear();
						visitedMap.put(h+","+v,h+","+v);
						queue.add(new BfsPoint(h+","+v,bfsPoint));
						stapFlag = true;
						break;
					}
					if(array[h][v].equals("O")) {
						visitedMap.put(h+","+v,h+","+v);
						queue.add(new BfsPoint(h+","+v,bfsPoint));
						continue;
					}
				} else {
					visitedMap.put(h+","+v,h+","+v);
				}
			}
		}
		if(!queue.isEmpty()) {
			BfsPoint bfsPoint = queue.poll();//出队操作
			while(bfsPoint!=null) {
				String positionSplit[] = bfsPoint.position.split(",");
				int horizontal = Integer.parseInt(positionSplit[0]);
				int vertical = Integer.parseInt(positionSplit[1]);
				if((!"S".equals(array[horizontal][vertical]))&&(!"E".equals(array[horizontal][vertical]))) {
					array[horizontal][vertical] = "*";
				}
				bfsPoint = bfsPoint.beforePoint;
			}
		} else {
			System.out.println("迷宫无解");
		}
	}
	
	/**
	 * 广度优先搜索存储的点位类
	 */
	class BfsPoint {
		
		private String position;//位置
		
		private BfsPoint beforePoint;//上一个点
		
		public BfsPoint(String position,BfsPoint beforePoint) {
			this.position = position;
			this.beforePoint = beforePoint;
		}

		public String getPosition() {
			return position;
		}

		public void setPosition(String position) {
			this.position = position;
		}

		public BfsPoint getBeforePoint() {
			return beforePoint;
		}

		public void setBeforePoint(BfsPoint beforePoint) {
			this.beforePoint = beforePoint;
		}
		
	}
	
	/**
	 * 深度优先搜索
	 * @param array 迷宫数组
	 * @param mazeSize 迷宫尺寸
	 */
	public void dfs(String[][] array,int mazeSize) {
		Stack<String> stack = new Stack<>();
		Map<String,String> visitedMap = new HashMap<>();//定义一个集合，存储所有已被访问过的节点
		int horizontal = 0,vertical = 0;//定义起始位置
		//final String[] positions = {"0,-1","0,1","-1,0","1,0"};//左、右、上、下
		final String[] positions = {"0,1","1,0","0,-1","-1,0"};//右、下、左、上
		int h = 0,v = 0;
		boolean stop = false;
		while(!stop) {
			int successCount = 0;
			/** 随机走法
			List<Integer> list = Stream.of(0,1,2,3).collect(Collectors.toList());
			for(int i=0;i<list.size();) {
				int choice = ThreadLocalRandom.current().nextInt(list.size());
				choice = list.remove(choice);
				String[] splits = positions[choice].split(",");
				h = horizontal + Integer.parseInt(splits[0]);
				v = vertical + Integer.parseInt(splits[1]);
				if(canMove(h,v,mazeSize,array,visitedMap)) {
					if(array[h][v].equals("E")) {
						//System.out.print("("+h+","+v+")");
						stop = true;
						successCount++;
						break;
					}
					if(array[h][v].equals("O")) {
						horizontal = h;
						vertical = v;
						visitedMap.put(horizontal+","+vertical,horizontal+","+vertical);
						stack.push(horizontal+","+vertical);
						//System.out.print("("+horizontal+","+vertical+")->");
						successCount++;
						break;
					}
				}
			}
			*/
			//遍历右、下、左、上四个走法
			for(String each:positions) {
				String[] splits = each.split(",");
				h = horizontal + Integer.parseInt(splits[0]);
				v = vertical + Integer.parseInt(splits[1]);
				if(canMove(h,v,mazeSize,array,visitedMap)) {
					if(array[h][v].equals("E")) {
						//System.out.print("("+h+","+v+")");
						stop = true;
						successCount++;
						break;
					}
					if(array[h][v].equals("O")) {
						horizontal = h;
						vertical = v;
						visitedMap.put(horizontal+","+vertical,horizontal+","+vertical);
						stack.push(horizontal+","+vertical);
						//System.out.print("("+horizontal+","+vertical+")->");
						successCount++;
						break;
					}
				}
			}
			if(successCount==0) {
				if(!stack.isEmpty()) {
					String pops[] = stack.pop().split(",");
					horizontal = Integer.parseInt(pops[0]);
					vertical = Integer.parseInt(pops[1]);
					array[horizontal][vertical] = "*";
				}else {
					System.out.println("迷宫无解");
					break;
				}
			}
		}
		while(!stack.empty()){
			String pops[] = stack.pop().split(",");
			array[Integer.parseInt(pops[0])][Integer.parseInt(pops[1])] = "*";
		}
	}
	
	/**
	 * 判断点位是否可以移动
	 * @param horizontal 横坐标
	 * @param vertical 纵坐标
	 * @param mazeSize 迷宫尺寸
	 * @param array 整个迷宫数组
	 * @param visitedMap 被访问过的集合
	 * @return 是否可以移动（true：可以；false：不可以）
	 */
	private boolean canMove(int horizontal,int vertical,int mazeSize,String[][] array,Map<String,String> visitedMap) {
		if((horizontal<mazeSize&&horizontal>-1)&&(vertical<mazeSize&&vertical>-1)&&
		   (visitedMap.get(horizontal+","+vertical)==null)&&(!array[horizontal][vertical].equals("R"))) {
			return true;
		}else {
			return false;
		}
	}
	
	/**
	 * 创建迷宫
	 * 1、始终将起始点放在左上角，记为S
	 * 2、始终将起终点放在右下角，记为E
	 * 3、路障记为R
	 * 4、其它可走道路记为O（大写字母O，不是数字0）
	 * 5、从S走向E的一条有效路线用*标记
	 * @param mazeSize 迷宫尺寸
	 * @return String[][] 整个迷宫数组
	 */
	private String[][] createMaze(int mazeSize) {
		final int totalSize = mazeSize*mazeSize;
		String array[] = new String[totalSize];
		Arrays.fill(array,0,array.length,"O");
		array[0] = "S";
		array[array.length-1] = "E";
		//路障随机数量设置为总量的20%
		int roadBlock = (int) ((totalSize-2)*0.2);
		List<Integer> list = IntStream.range(1,array.length-1).boxed().collect(Collectors.toList());
		while(roadBlock>0) {
			int index = ThreadLocalRandom.current().nextInt(list.size());
			array[list.remove(index)] = "R";
			roadBlock--;
		}
		//将一维数组转成二维数组
		int count = 0;
		String out[][] = new String[totalSize][totalSize];
		for(int i=0;i<mazeSize;i++) {
			for(int j=0;j<mazeSize;j++) {
				out[i][j] = array[count++];
			}
		}
		return out;
	}
	
	/**
	 * 打印输出
	 * @param array 迷宫数组
	 * @param mazeSize 迷宫尺寸
	 */
	private void printMaze(String[][] array,int mazeSize) {
		final String emptyStr = " ";
		for(int i=0;i<mazeSize;i++) {
			for(int j=0;j<mazeSize;j++) {
				System.out.print(array[i][j]+emptyStr);
			}
			System.out.println();
		}
		System.out.println("--------------------");
	}
	
	/**
	 * 计算两点之间的距离
	 * @param point1 点1
	 * @param point2 点2
	 * @return double 两点间距离
	 */
	public static double distance(String point1, String point2) {
		String[] p1 = point1.split(",");
		String[] p2 = point2.split(",");
		return Math.sqrt(Math.pow(Integer.parseInt(p2[0])-Integer.parseInt(p1[0]),2)+Math.pow(Integer.parseInt(p2[1])-Integer.parseInt(p1[1]),2));
	}
	
}